package data_structure.tree.binaryTree;

import cn.hutool.core.lang.Assert;
import lombok.Data;
import lombok.experimental.Accessors;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName : data_structure.tree.binaryTree.BinartTreeDemo
 * @Description : 类描述
 * Created by cyd on 2021-03-09 20:47:32
 */
public class BinartTreeDemo {
    public static void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "songjiang");
        HeroNode heroNode2 = new HeroNode(2, "likui");
        HeroNode heroNode3 = new HeroNode(3, "lichong");
        HeroNode heroNode4 = new HeroNode(4, "wuyong");
        HeroNode heroNode5 = new HeroNode(5, "guansheng");

        heroNode1.setLeft(heroNode2);
        heroNode1.setRight(heroNode3);
        heroNode3.setRight(heroNode4);
        heroNode3.setLeft(heroNode5);
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(heroNode1);

//        binaryTree.preOrder();
//        System.out.println("------------------");
//        binaryTree.infixOrder();
//        System.out.println("------------------");
//        binaryTree.postOrder();

//        System.out.println("------------------");
//        System.out.println(binaryTree.preOrderFind(3));
//        System.out.println(binaryTree.infixOrderFind(3));
//        System.out.println(binaryTree.postOrderFind(3));

        HeroNode heroNode = binaryTree.deleteNode(3);
        System.out.println(heroNode);

    }

}

@Data
class BinaryTree {
    private HeroNode root;

    // 树的前序遍历
    public void preOrder() {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    // 树的中序遍历
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    // 树的后序遍历
    public void postOrder() {
        if (root != null) {
            root.postOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    // 树的前序查找
    public HeroNode preOrderFind(Integer index) {
        if (root != null) {
            return root.preFind(index);
        } else {
            System.out.println("当前二叉树为空，无法查找");
            return null;
        }
    }

    // 树的中序查找
    public HeroNode infixOrderFind(Integer index) {
        if (root != null) {
            return root.infixFind(index);
        } else {
            System.out.println("当前二叉树为空，无法查找");
            return null;
        }
    }

    // 树的后序查找
    public HeroNode postOrderFind(Integer index) {
        if (root != null) {
            return root.postFind(index);
        } else {
            System.out.println("当前二叉树为空，无法查找");
            return null;
        }
    }

    /**
     * 二叉树的删除,找到前一个节点
     */
    public HeroNode deleteNode(Integer index) {
        Assert.notNull(index);
        if (root == null) {
            throw new RuntimeException("节点为空,不饿能删除");
        }
        if (root.getNo().equals(index)) {
            root = null;
            System.out.println("清空了树");
            return null;
        }
        Map<String, HeroNode> map = root.findDeletePreNode(index);
        HeroNode pre;
        HeroNode result = null;
        if (map.get("left") != null) {
            pre = map.get("left");
            result = pre.getLeft();
            pre.setLeft(null);
        }
        if (map.get("right") != null) {
            pre = map.get("right");
            result = pre.getRight();
            pre.setRight(null);
        }
        return result;

    }
}

@Data
@Accessors(chain = true)
class HeroNode {
    private Integer no;
    private String name;
    private HeroNode left;
    private HeroNode right;


    public HeroNode(Integer no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}';
    }

    // 前序遍历
    public void preOrder() {
        // 先输出父节点
        System.out.println(this);
        // 左节点继续前序遍历
        if (left != null) {
            left.preOrder();
        }
        // 右节点继续前序遍历
        if (right != null) {
            right.preOrder();
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (left != null) {
            left.infixOrder();
        }
        System.out.println(this);
        if (right != null) {
            right.infixOrder();
        }
    }

    public void postOrder() {
        if (left != null) {
            left.postOrder();
        }
        if (right != null) {
            right.postOrder();
        }
        System.out.println(this);
    }

    // 前序查找
    public HeroNode preFind(Integer index) {
        if (index.equals(getNo())) {
            return this;
        }
        HeroNode resHeroNode = null;

        if (getLeft() != null) {
            resHeroNode = getLeft().preFind(index);
        }

        if (getRight() != null) {
            resHeroNode = getRight().preFind(index);
        }

        return resHeroNode;
    }

    // 中序查找
    public HeroNode infixFind(Integer index) {

        HeroNode resHeroNode = null;
        if (getLeft() != null) {
            resHeroNode = getLeft().infixFind(index);
        }

        if (index.equals(getNo())) {
            return this;
        }

        if (getRight() != null) {
            resHeroNode = getRight().infixFind(index);
        }

        return resHeroNode;
    }

    // 后序查找
    public HeroNode postFind(Integer index) {

        HeroNode resHeroNode = null;
        if (getLeft() != null) {
            resHeroNode = getLeft().postFind(index);
        }

        if (getRight() != null) {
            resHeroNode = getRight().postFind(index);
        }

        if (index.equals(getNo())) {
            return this;
        }

        return resHeroNode;
    }

    /*
     * 找到要删除的子节点,并返前一个节点
     */
    public Map<String, HeroNode> findDeletePreNode(Integer index) {
        Assert.notNull(index);
        Map<String, HeroNode> map = new HashMap<>();
        if (left != null &&
                left.getNo().equals(index)) {
            map.put("left", this);
            return map;
        }
        if (right != null &&
                right.getNo().equals(index)) {
            map.put("right", this);
            return map;
        }
        if (left != null) {
            map = left.findDeletePreNode(index);
        }
        if (right != null) {
            map = right.findDeletePreNode(index);
        }
        return map;
    }
}
